package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 44. 通配符匹配
 * @date 2025/5/9 18:50
 */
public class E44 {

    /**
     * <h3>方法一：动态规划</h3>
     *
     * @param s 源字符串
     * @param p 模式字符串
     * @return 是否匹配
     */
    public boolean isMatch(String s, String p) {
        // 1. 转成字符数组
        char[] source = s.toCharArray();
        char[] pattern = p.toCharArray();
        // 2. 准备dp数组
        boolean[][] dp = new boolean[pattern.length + 1][source.length + 1];
        // 3. 初始化dp数组
        // 3.1 dp[0][0] = true;
        dp[0][0] = true;
        // 3.2 考虑源字符串为空的时候
        for (int i = 1; i <= pattern.length; i++) {
            if (pattern[i - 1] == '*') {
                dp[i][0] = dp[i - 1][0];
            }
        }
        // 3.3 考虑模式字符串为空的时候
        // 4. 填充dp数组
        for (int i = 1; i <= pattern.length; i++) {
            for (int j = 1; j <= source.length; j++) {
                // 4.1 模式字符串最后一位是?
                if (pattern[i - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 4.2 模式字符串最后一位是*
                else if (pattern[i - 1] == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
                // 4.3 模式字符串最后一位是普通字符
                else {
                    dp[i][j] = dp[i - 1][j - 1] && pattern[i - 1] == source[j - 1];
                }
            }
        }
        // 5. 返回结果
        return dp[pattern.length][source.length];
    }
}
